#include <iostream>
#include "algraph.h"
#include "sqqueue.h"
using namespace std;
//拓外排序算法TopologicalSort(G)

//对图G进行拓外排序，按拓外有序的领序输出顶点
template <typename V, typename E, int M>

void TopologicalSort(ALGraph<V, E, M> G)
{

    //计算每个顶点的入度indegree[ ]
    int indegree[M] = {0}; //全部初始化为等

    for (int v = 0;v < G.vexnum; v++)
    {

        for (auto p = G.vexs[v].firstarc; p; p = p->nextarc)
        {
            int w = p->adjvex;

            indegree[w]++;
        }
    }

    //所有入度为等的顶点，入从列Q

    SqQueue<int, M> Q;
    InitQueue(Q);
    for (int v = 0; v < G.vexnum; v++)
             if (indegree[v] == 0)
                 EnQueue(Q, v);

//逐个输出入度为等的顶点并删除之，并将新的入人度为等的顶点入从列
     int count = 0;
     while (!QueueEmpty(Q))
{
            //歇一个人废为等的项点v

            int v;

            DeQueue(Q, v);

            //输出入废为等的项点v

            std::cout << G.vexs[v].data;

            count++;
            //项点v所有邻接点入度减1
            for (auto p = G.vexs[v].firstarc; p; p = p->nextarc)
            {
                int w = p->adjvex;

                indegree[w]--;

                //如果W人废为等则入财列

                if (indegree[w] == 0)
                    EnQueue(Q, w);
            }
}

//结论:如果图中存在回路，提示信息/抛出异常

if (count < G.vexnum)
     throw "Graph has a cycle";
}

//主函数测试拓外排序
int main()
{
    //建立有向无环图
    // G = ({A,B,C,D,E}, {AB, AC, BD, BE, CD,CE, DE})
    ALGraph<char, int> G;
    //却始化
    InitGraph(G);
    //添加项点
    auto a = AddVertex(G, 'A');
    auto b = AddVertex(G, 'B');
    auto C = AddVertex(G, 'C');
    auto d = AddVertex(G, 'D');
    auto e = AddVertex(G, 'E');
    //添加边
    AddArc(G, a, b, 1);
    AddArc(G, a, C, 1);
    AddArc(G, b, d, 1);
    AddArc(G, b, e, 1);
    AddArc(G, C, d, 1);
    AddArc(G, C, e, 1);
    AddArc(G, d, e, 1);
    //拓外排序
    cout << "TopologicalSort: ";
    TopologicalSort(G);
    return 0;
}